/**
 * @program: data_structures_algorithms
 * @description: 链表排序-快速排序思想
 * @author: lld
 * @create: 2021-04-10 19:27
 **/
public class ListQuickSort {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode4.next=listNode2;
        listNode2.next=listNode1;
        listNode1.next=listNode3;
        listNode3.next=listNode5;

        ListNode listNode = quickSort(listNode4, null);
        System.out.println(listNode);
    }
    /**
    * @Description: 由于链表不能知道前一个节点，基准值：head,进行头插尾插
    **/
    private static ListNode quickSort(ListNode head,ListNode end){
//        返回条件
        if(head ==end || head.next ==end) return head;
        ListNode lhead=head,utail=head,p=head.next;
        while (p!=end){
//            保存p.next
            ListNode next=p.next;
//            头插
            if(p.val<head.val){
                p.next=lhead;
                lhead=p;
            }else {
                utail.next=p;
                utail=p;
            }
            p=next;
        }
        utail.next=end;
        ListNode node=quickSort(lhead, head);
        head.next=quickSort(head.next, end);
        return node;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "{" + val +
                    "," + next +
                    '}';
        }
    }

}


